package leetcode;
import java.util.Scanner;
public class DP {//01背包问题空间优化过
        public static void main(String[] args) {
            Scanner sc=new Scanner(System.in);
            int n=sc.nextInt();
            int V=sc.nextInt();//背包容量
            int[]v=new int[n+1];//体积
            int[]w=new int[n+1];//价值
            int[]f=new int[V+1];
            for(int i=1;i<=n;i++) {
                v[i]=sc.nextInt();
                w[i]=sc.nextInt();
            }
            for(int i=1;i<=n;i++) {
                for(int j=V;j>=v[i];j--) {


                    f[j]=Math.max(f[j], f[j-v[i]]+w[i]);

                }
            }
            System.out.println(f[V]);
        }


}
